// 快速排序: 
// 1、选择基数: 从序列中选择一个基数（可以随便第几位） 
// 2、分割操作：将序列中小于基准的元素放在基准的左边，大于基准的元素放在基准的右边
// 3、递归排序：对基准左右两边的子序列分别进行快速排序，直到子序列的长度为1或0。
function QuickSort(arr) {
  if(arr.length <= 1) return arr
  let basic = arr[Math.floor(arr.length / 2)]
  let left = []
  let right = []
  let center = []
  for(let i of arr) {
    if(i < basic) {
      left.push(i)
    }else if(i > basic){
      right.push(i)
    }else {
      center.push(i)
    }
  }
  return QuickSort(left).concat(...center, QuickSort(right))
}
let arr = [5, 2, 6, 3, 7, 5, 5, 4, 1, 3] 
// 5 2 3 3 1 5 5 4 7 6
// const a = QuickSort(arr)
// console.log(a);

// 复杂度更低的方法
function quicksort(arr, left = 0, right = arr.length - 1) {
  if(left >= right) return
  const index = left
  const privot = arr[left]
  while(left < right) {
    // 因为后面基数需要和left调换位置，所以这里必须是先遍历right，当遍历到right=left时，这时arr[left]肯定时小于基数的
    while(left < right && arr[right] >= privot) {
      right--
    }
    while(left < right && arr[left] <= privot) {
      left++
    }
    if(left !== right) {
      [arr[left], arr[right]] = [arr[right], arr[left]]
    }
  }
  [arr[index], arr[left]] = [arr[left], arr[index]]
  quicksort(arr, index, left - 1)
  quicksort(arr, right + 1, arr.length - 1)
}
// quicksort(arr)
console.log(arr);
// 找一个基数，让左边的都比基数小，右边的都比基数大
function test(arr, left = 0, right = arr.length - 1) {
  if(left >= right) return
  const index = left
  const basic = arr[left]
  while(left < right) {
    while(left < right && arr[right] >= basic) {
      right--
    }
    while(left < right && arr[left] <= basic) {
      left++
    }
    if(left !== right) {
      [arr[left], arr[right]] = [arr[right], arr[left]] //交换数据
    }
  }
  // 让基数换位到中间
  [arr[index], arr[left]] = [arr[left], arr[index]]
  // 此时left和right值是相等的
  // 此时左边的都比基数小（但是左边的顺序还不确定，所以还需要排序），右边的都比基数大
  test(arr, index, left - 1)
  test(arr, right + 1, arr.length - 1)
}